package simple;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 1.两数之和
 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
 * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
 * */


public class TwoSum {
    // 暴力遍历法：双重遍历 时间复杂度：O(n^2) 空间复杂度：O(1)
    public int[] twoSum(int[] nums, int target){
        for (int i = 0; i < nums.length-1; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (target-nums[j] == nums[i]){
                    return new int[]{i,j};
                }
            }
        }
        return null;
    }


    // map查找 时间复杂度:O(n) 空间复杂度：O(n)
    /**
     * ps: 这个方法其实有弊端，因为是使用HashMap来做的，实际上没
     * 法保证在HashMap中查找效率是 O(1)，因为存在Hash碰撞，而
     * HashMap采用了链表以及红黑树来应对Hash碰撞时的查找效率降低到 O(n)
     * 的情况的，Hash碰撞的情况下，HashMap的查询效率最多只能优化到 O(log n)
     * 所以，只能说这个方法只能做到时间复杂度趋近于 O(n)
     * */
    public int[] twoSum1(int[] nums, int target){
        Map<Integer,Integer> m = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(m.containsKey(target - nums[i])){
                return new int[]{m.get(target - nums[i]), i};
            }else {
                m.put(nums[i], i);
            }
        }
        return null;
    }

    // main 方法
    public static void main(String[] args) {
        TwoSum ts = new TwoSum();
        int[] s = ts.twoSum1(new int[]{2, 5, 8, 9, 6}, 10);
        System.out.println(Arrays.toString(s));
    }
}
